00100	                     COMPUTER SCIENCE DEPARTMENT
00200	                         STANFORD UNIVERSITY
00300	
00400	
00500	CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1970
00600	                            MIDTERM EXAM
00700	                        Open Books and Notes
00800	
00900	
01000		Write  LISP  functions  as  follows  using  the  M-expression
01100	notation used in class:
01200	
01300		1.  a. rcycle[u]  is obtained from the list  u  by moving the
01400	last element to the first position.  Thus
01500	
01600		rcycle[(A B C D)] = (D A B C).
01700	
01800		b. lcycle[u]  is obtained from the list   u   by  moving  the
01900	first element to the last position.  Thus
02000	
02100		lcycle[(A B C D)] = (B C D A).
02200	
02300		2.  pairs[u,v]   is  the  list of all pairs of elements, each
02400	pair taking one element from  u  and one from  v. Thus
02500	
02600		pairs[(A B C),(D E)] = ((A D) (A E) (B D) (B E) (C D) (C E)).
02700	
02800	Observe the ordering given in the example.
02900	
03000		3. testr[u,f,p,w]  is obtained from the S-expression   u   as
03100	follows:  If no subexpression of  u  satisfies the predicate  p, then
03200	 w[u]  is the result.  If there is such an expression, say   m,  then
03300	 f[m]   is  the result. If there are several such  m, then any  f[m] 
03400	will do.
03500	
03600	                     COMPUTER SCIENCE DEPARTMENT
03700	                         STANFORD UNIVERSITY
03800	
03900	
04000	CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1970
04100	
04200	
04300	                      SOLUTIONS TO THE MIDTERM
04400	
04500	1a.	rcycle u ← if n u then NIL 
04600	
04700				  else [λw. a w . reverse d w] reverse u.
04800	
04900	 b.	lcycle u ← if n u then NIL else d u * list a u.
05000	
05100	
05200	2. 	pairs[u,v] ← if n u then NIL else mapcar[v,λx. list[a u,x]]*
05300				pairs[d u,v].
05400	
05500	Instead of using %mapcar% we can use an auxiliary function, e.g.
05600	
05700		pairs[u,v] ← if n u then NIL else paira[a u,v]*pairs[d u,v],
05800	
05900	where
06000	
06100		paira[x,v] ← if n v then NIL else list[x,a v].paira[x,d v].
06200	
06300	Still another solution is
06400	
06500		pairs[u,v] ← pair1[u,v,v],
06600	
06700	where
06800	
06900		pair1[u,v,w] ← if n u then NIL else if n w then pair1[d u,v,v]
07000					else list[a u,a w].pair1[u,v,d w].
07100	
07200	
07300	3. 	testr[u,f,p,w] ← [λx. if n x then w u else f d x] find[u,p],
07400	
07500	where
07600	
07700		find[u,p] ← if p u then 'BUZZ.u else if at u then NIL
07800			else [λx. if n x then find[d u,p] else x] find[a u,p].
07900	
08000	There  are  many more ways to solve this problem.  One way is to list
08100	all the sub-expressions  of  %u%  and  to  search  the  list  for  an
08200	expression satisfying %p.  Thus, we may write
08300	
08400		subs[u] ← subs1[u,NIL],
08500	
08600		subs1[u,v] ← u.[if at u then v else subs1[a u,subs1[d u,v]]],
08700	
08800		search[z,f,p,w,u] ← if n z then w u else if p a z then f a z
08900			else search[d z,f,p,w,u],
09000	
09100	and
09200	
09300		testr[u,f,p,w] ← search[subs u,f,p,w,u].
09400	
09500	
09600		The most frequent errors in the second  problem  involved not
09700	noting  that  the base case is when the lists are null and in using .
09800	instead of * for concatenating.
09900	
10000		The  most  frequent  errors in the third problem involved not
10100	noting that %NIL% is an  atom  like  any  other  and  neglecting  the
10200	possibility that %NIL% is a legitimate possible  sub-expression  that
10300	might satisfy %p% and a legitimate possible value of %f[m].
10400	
10500		On the whole, the results of the exam were satisfactory.
10600	
10700		GG graded 1a and 1b, JMC graded 2 and 3.